package cn.gok.day2;

import java.util.Scanner;

/**
 * @ClassName Fibonacci
 * @Description TODO
 * @Author HP
 * @Date 20:13 2022/7/5
 * @Version 1.0
 *
 * 1 1 2 3 5 ....
 * 斐波那契数列，从第三个开始，都是前两个数的和
 **/
public  class Fibonacci {
//    利用递归的方法实现
    public static int getNum(int n){
        if(n==1||n==2){
            return 1;
        }
        if(n>2){
            return getNum(n-1)+getNum(n-2);
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入想要查询第几个斐波那契数列：");
        int n=scanner.nextInt();
//        int tp=getNum(n);
        long tp =getForNum(n);
        if(tp!=-1){
            System.out.println("第"+n+"个斐波那契数列是："+tp);
        }else{
            System.out.println("请输入正整数哦~");
        }
    }
//    很慢，不推荐
    public static long getForNum(int n){
        if(n==1||n==2){
            return 1;
        }
        if(n>2){
            long arr[]=new long[n];
            arr[0]=arr[1]=1;
            for (int i = 2; i < n; i++) {
                arr[i]=(long) (arr[i-1]+arr[i-2]);
//                测试证明，第888个数字太大了会导致溢出，出现负数，连long都不能解决
//                System.out.println((long) arr[i]);
            }
            return arr[n-1];
        }
        return -1;
    }
}
